In present and future communication standards, such as the cellular 3rd Generation Partnership Project, Long Term Evolution (3GPP-LTE), LTE-Advanced, and Worldwide Interoperability for Microwave Access (WiMAX), both the base station (BS) and user equipments (UE) have multiple antennas. These communication systems are generally referred to as multiple input multiple output (MIMO) systems. In conventional cellular systems, the transmissions by a BS to multiple users are organized into time sequential frames, each of which is divided into a series of subframes, and a single user is assigned for transmission in a respective subframe. However in more recent systems, multiple users can be scheduled for transmission simultaneously using MU-MIMO precoding algorithms.
A conventional arrangement for a cellular system is illustrated in FIG. 1 where the BS has multiple antennas (1, 2, 3) that are fed respective signals (y1, y2, y3) destined for the user equipment UE-1, UE-2. Each UE has one or more antennas, with UE-1 shown as having two antennas (1, 2) that deliver signals v1, v2, respectively, and UE-2 having two antennas (3, 4) that deliver signals v3, v4. The downlink from antenna 1 of the BS provides a transmission to each antenna (h11, h12, h13, h14) and similar transmissions are provided by antenna 2 (unnumbered) and antenna 3 (h31, h32, h33, h34) of the BS. The received signal can be represented by a matrix v of signals v1-v4, with T is the transpose operation for the vector, and can further be expressed as channel matrix Hy.
The MIMO Channel
The downlink channel between a base station and several UEs may be represented as a matrix H, where the number of rows (i) in the matrix is equal to the sum of antennas of the several UEs and the number of columns (j) in the matrix is equal to the number of transmit antennas at the base station. For FIG. 1, there are 4 rows for the four antennas (1-4) and 3 columns for the 3 antennas at the BS. The (i,j)th entry to the matrix H represents the complex channel gain hij between the ith transmit antenna and jth receive antenna, as shown in FIG. 1. In particular, the complex channel gain hij represents the amplification (or attenuation) that the transmitted signal undergoes in the wireless downlink channel.
The downlink channel H is represented by two downlinks H1 and H2 from BS to each of the UE-1 and UE-2, respectively, and each downlink is represented by a respective matrix H1, H2 having the row and column content as described. For example, the H1 downlink matrix has signals h11, h12, h31, h12, h22 and h32, as shown in FIG. 1.
Chordal Distance
Some conventional algorithms employed by the base station to schedule transmissions on a downlink to the BEs are based on the chordal distance between the channel matrix spaces of two users. This metric determines how ‘far apart’ the two sub-spaces are located. A discussion of chordal distances appears in K. Ko, J. Lee, “Low complexity MU MIMO scheduling with chordal distance”, IEEE CISS March, 2008.
FIG. 2 illustrates a simple example where a base station 200 transmits to two mobiles over two time subframes. In the first time subframe transmission is to mobile apparatus 201 and in the second time subframe, transmission is to mobile apparatus 202.
Given the different characteristics of the transmissions, the two transmissions do not interfere with each other. By way of representation, let 1 denote a transmission and 0 denote no transmission. The channel of the mobile apparatus 201 can therefore be written as [1 0], and the channel of mobile apparatus 202 can be written as [0 1] respectively. Thus, another way of stating the non-interference condition is to observe that the channel vectors are orthogonal, that is, there is no interference in time or frequency and no overlap. The chordal distance measures the degree of orthogonality of the two channels. In this example, the channels have maximum chordal distance.
The impact of the chordal distance can be appreciated by assuming that a MU-MIMO algorithm picks up two users (User 1 and User 2) in the downlink. Also, assume that there is a precoder T1, and T2 for each user, and that the precoder used is block diagonalization. Under these circumstances, given a noise vector z, a data stream s and the transmitted signal vector at the base station x, the equations representing what was transmitted at the base station and what was received at the mobile can be represented as y1=H1x+z1 and y2=H2x+z2 where x=T1s1+T2s2 
Precoder T1 is designed so that it lies in the nullspace of the other user's channel H2 so that the signal for User 1 does not cause interference for User 2. Therefore, the precoder is set to T1=N(H2). However doing so modifies the channel of User 1 from H1 to H1T1, which could lead to a loss in performance. This loss can be minimized if the channels of the two users are as orthogonal as possible. The chordal distance measures this degree of orthogonality or separation between the two channels.
MU-MIMO Scheduling
FIGS. 3(a) and 3(b) illustrates an example of SU-MIMO and MU-MIMO scheduling. For SU-MIMO of FIG. 3(a), the base station selects (schedules) one mobile apparatus in each time subframe to which it transmits, while for MU-MIMO in FIG. 3(b), multiple users may be selected. In the example of FIGS. 3(a) and 3(b), the scheduling of three mobile apparatuses are shown over two time subframes. For SU-MIMO of FIG. 3(a), the base station 200 schedules mobile apparatus 300 in time subframe 1 (represented by [1 0]) and mobile apparatus 301 in time subframe 2 (represented by [0 1]). Mobile apparatus 302 is unscheduled (represented by [0 0]). For MU-MIMO of FIG. 3(b), the base station 200 schedules mobile apparatus 300 and 301 in time subframe 1 and mobile apparatus 300 and 302 in time subframe 2.
Multiple mobile apparatuses may be connected to a single base station, which serves all of them in the downlink. However due to the limits in signal processing technology, the base station may not be able to transmit data to all of them at once. In most cellular systems, the service time of the base stations is divided into subframes. For example in 3GPP LTE, the base station decides which mobile to transmit for every subframe of 0.1 ms.
The process that the base station utilizes to decide which user or users to transmit to every subframe is called scheduling. In LTE Rel-8, the base station schedules only a single user in a subframe (over a given frequency band). This is called Single User (SU-MIMO) scheduling. In higher versions of LTE, the base station may select multiple users to transmit to in a subframe. This is called Multiple User (MU-MIMO) scheduling.
Assume that there are K users in a cell who are eligible for receiving data in the downlink in a frame. The base station selects a subset of these users for transmission in a frame as scheduling of all users may lead to performance degradation for all users. There are many algorithms that have been proposed for user selection which maximize different metrics.
For example, several previous algorithms attempt to maximize the sum capacity. However these algorithms are of high computational complexity. Other algorithms attempt to reduce complexity while still maximizing the sum capacity. In cellular systems, however, proportional fairness is usually considered a better metric than sum capacity, as the latter metric tends to pick users based only on their signal strengths. Thus, users that are closer to the base station will get scheduled consistently which is unfair for the cell edge users. Previous MU-MIMO scheduling algorithms with Proportional Fairness (PF) metrics still require an exhaustive search, which requires high computational complexity.
Proportional Fairness
The round-robin scheduler and the proportional far scheduler are examples of two well-known UE schedulers. The round-robin scheduler is one of the simplest schedulers, which assign resource blocks (e.g., time subframes, frequency bands) to each UE in equal portions and in circular order without priority. Proportional fair schedulers (PFS) utilize a fairness consideration among UEs. The PFS schedules a UE when its instantaneous channel quality is high relative to its own average channel condition over time, i.e., it assigns resource block m to UE k if k= k, where
  k  =                    arg        ⁢                                  ⁢        max                              i          =          1                ,        ⋯        ⁢                                  ,        K              ⁢                            R          i                ⁡                  (          m          )                            T        i            where K is the total number of UEs, Ri(m) is the instantaneous achievable rate of the ith UE in resource block m, and Ti is the long-term average rate of the ith UE. The PFS has been applied in LTE cellular systems.
FIG. 4 illustrates exemplary steps of conventional MU-MIMO signal processing. MU-MIMO signal processing in the downlink can be explained in the most general terms as follows:
Step S401: Base station and a set of K users who are associated to the base station are identified.
Step S402: At each scheduling instant the base station uses the User Selection Algorithm (such as MU-MIMO scheduling) to decide a subset of users who would receive data in a downlink.
Step S403: The base station transmits to the set of users using a MU-MIMO precoding algorithm at rates set for each user.
The user selection method depends on the precoding used, and the performance of the precoding is affected by the users chosen. Where there are multiple users, all possible pairs of users must be evaluated, resulting in a high number of evaluations. One protocol is to fix one user and to search all other users for a pair, and in this way to calculate a proportional fairness (PF) metric for all users.
When multiple users are scheduled simultaneously for transmission, the PF metric has been modified to the sum of PF metrics of each user in the set of scheduled users where the optimal set is found by exhaustive search. However, this method still requires high computational complexity.